/*
 * ApostolicoGiancarlo.cpp
 *
 *  Created on: 01-09-2013
 *      Author: Krzychu
 */

#include "ApostolicoGiancarlo.h"

#include "Config.h"

#include <stdio.h>
#include <string.h>

#define MAX(a, b) (a > b) ? a : b

ApostolicoGiancarlo::ApostolicoGiancarlo()
{

}

ApostolicoGiancarlo::~ApostolicoGiancarlo()
{

}

std::string ApostolicoGiancarlo::getName()
{
	return "Apostolico Giancarlo";
}

searchResult ApostolicoGiancarlo::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j, k, s, shift;

	/* Preprocessing */
	int* suff = pre_suffixes(pattern);
	int* bmGs = pre_good_suffix_shift(pattern);
	int* bmBc = pre_bad_character_shift(pattern);
	int* skip = new int[patternSize];

	for (int l = 0; l < patternSize; l++)
	{
		skip[l] = -1;
	}

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = patternSize - 1;
		while (i >= 0)
		{
			k = skip[i];
			s = suff[i];
			if (k > 0)
				if (k > s)
				{
					if (i + 1 == s)
					{
						i = (-1);
					}
					else
					{
						i -= s;
					}
					break;
				}
				else
				{
					i -= k;
					if (k < s)
					{
						break;
					}
				}
			else
			{
				if (pattern[i] == text[i + j])
				{
					--i;
				}
				else
				{
					break;
				}
			}
		}
		if (i < 0)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
			skip[patternSize - 1] = patternSize;
			shift = bmGs[0];
		}
		else
		{
			skip[patternSize - 1] = patternSize - 1 - i;
			shift = MAX(bmGs[i], bmBc[text[i + j]]  -patternSize + 1 + i);
		}
		j += shift;
		memcpy(skip, skip + shift, (patternSize - shift) * sizeof(int));
		memset(skip + patternSize - shift, 0, shift * sizeof(int));
	}

	return result;
}

